package lpg;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Dfa
{
    Dfa(Control control)
    {
        this.control    = control;
        this.option     = control.option;
        this.grammar    = control.grammar;
        this.base       = control.base;

        shift.insert(null);
        conflicts.add(0);
        assert (shift.size() == 1 && conflicts.size() == 1);
    }

    void processDFA()
    {
        makeLr0();
        buildPredecessorsMap();
    }

    //
    // This procedure constructs an LR(0) automaton.
    //
    private void makeLr0()
    {
        statset.insert(null, null); // skip the zeroth element !!!

        //
        // Kernel of the first state consists of the first item of the
        // rule produced by the Accept non-terminal.
        //
        assert (base.clitems.get(grammar.acceptImage).size() == 1);
        Node q = new Node(base.clitems.get(grammar.acceptImage).get(0));

        //
        // States are identified by their Kernel set of items. As states
        // are inserted in the table, they are threaded together via the
        // QUEUE component of STATE_ELEMENT. The variable STATE_ROOT points
        // to the root of the thread, and the variable STATE_TAIL points to the tail.
        //
        //   After constructing a state, Shift and Goto actions are
        // defined on that state based on a partition of the set of items
        // in that state. The partitioning is based on the symbols
        // following the dot in the items. The array PARTITION is used
        // for that partitioning. LIST and ROOT are used to construct
        // temporary lists of symbols in a state on which Shift or Goto
        // actions are defined.
        //   ntList and ntRoot are used to build temporary lists of
        // non-terminals.
        //
        int[] shiftAction = new int[grammar.numTerminals + 1];
        Arrays.fill(shiftAction, Util.OMEGA);
        int gotoSize = 0;
        int ntRoot = Util.NIL;
        BoundedIntArray ntList = new BoundedIntArray(grammar.numTerminals + 1, grammar.numSymbols);
        ntList.fill(Util.OMEGA);
        Node[] partition = new Node[grammar.numSymbols + 1];
        IntArrayList shiftList = new IntArrayList();
        IntArrayList list = new IntArrayList();

        //
        // Insert first state in statset and keep constructing states
        // until we no longer can.
        //
        for (int stateIndex = lr0StateMap(q); // insert initial state
             stateIndex < statset.size(); // and process next state until no more
             stateIndex++)
        {
            StateElement state = statset.element(stateIndex);
            //
            // Now we construct a list of all non-terminals that can be
            // introduced in this state through closure.  The CLOSURE of each
            // non-terminal has been previously computed in MKFIRST.
            //
            for (q = state.kernelItems;
                 q != null; // iterate over kernel set of items
                 q = q.next)
            {
                int itemNo = q.value;
                int symbol = base.itemTable[itemNo].symbol;  // symbol after dot
                if (grammar.isNonTerminal(symbol)) // Dot symbol
                {
                    if (ntList.get(symbol) == Util.OMEGA) // not yet seen
                    {
                        ntList.set(symbol, ntRoot);
                        ntRoot = symbol;

                        IntArrayList closureForSymbol = base.closure.get(symbol);
                        for (int k = 0, m = closureForSymbol.size(); k < m; k++)
                        {
                            int element = closureForSymbol.get(k);

                            if (ntList.get(element) == Util.OMEGA)
                            {
                                ntList.set(element, ntRoot);
                                ntRoot = element;
                            }
                        }
                    }
                }
            }

            //
            // We now construct lists of all start items that the closure
            // non-terminals produce.  A map from each non-terminal to its set
            // start items has previously been computed in MKFIRST. (CLITEMS)
            // Empty items are placed directly in the state, whereas non_empty
            // items are placed in a temporary list rooted at closureRoot.
            //
            Node closureRoot = null; // used to construct list of closure items
            Node closureTail = null;
            for (int symbol = ntRoot; symbol != Util.NIL; ntList.set(symbol, Util.OMEGA), symbol = ntRoot)
            {
                ntRoot = ntList.get(symbol);

                IntArrayList clitemsForSymbol = base.clitems.get(symbol);
                for (int k = 0, m = clitemsForSymbol.size(); k < m; k++)
                {
                    int itemNo = clitemsForSymbol.get(k);

                    Node newItem = new Node(itemNo);

                    if (base.itemTable[itemNo].symbol == grammar.empty) // complete item
                    {
                        newItem.next = state.completeItems;
                        state.completeItems = newItem;
                    }
                    else // closure item, add to closure list
                    {
                        if (closureRoot == null)
                            closureRoot = newItem;
                        else
                            closureTail.next = newItem;
                        closureTail = newItem;
                    }
                }
            }

            Node itemPtr = null;
            if  (closureRoot != null) // any non-complete closure items?
            {
                closureTail.next = state.kernelItems;
                itemPtr = closureRoot;
            }
            else  // else just consider kernel items
                itemPtr = state.kernelItems;

            //
            //   In this loop, the PARTITION map is constructed. At this point,
            // itemPtr points to all the non_complete items in the closure of
            // the state, plus all the kernel items.  We note that the kernel
            // items may still contain complete-items, and if any is found, the
            // COMPLETE_ITEMS list is updated.
            //
            list.clear();
            for (; itemPtr != null; itemPtr = itemPtr.next)
            {
                int itemNo = itemPtr.value;
                int symbol = base.itemTable[itemNo].symbol;
                if (symbol != grammar.empty)  // incomplete item
                {
                    int nextItemNo = itemNo + 1;

                    if (partition[symbol] == null) // PARTITION not defined on symbol
                    {
                        list.add(symbol);  // add to list
                        if (grammar.isNonTerminal(symbol))
                            gotoSize++;
                    }
                    Node p = partition[symbol];
                    Node tail = null;
                    for (; p != null; tail = p, p = p.next)
                    {
                        if (p.value > nextItemNo)
                            break;
                    }

                    Node r = new Node(nextItemNo, p);

                    if (p == partition[symbol]) // Insert at beginning
                        partition[symbol] = r;
                    else
                        tail.next = r;
                }
                else // Update complete item set with item from kernel
                {
                     Node p = new Node(itemNo, state.completeItems);
                     state.completeItems = p;
                }
            }

            //
            // We now iterate over the set of partitions and update the state
            // automaton and the transition maps: SHIFT and GOTO. Each
            // partition represents the kernel of a state.
            //
            for (int i = list.size() - 1; i >= 0; i--)
            {
                int symbol = list.get(i);
                int action = Util.OMEGA;

                //
                // If the partition contains only one item, and it is adequate
                // (i.e. the dot immediately follows the last symbol), and
                // READ-REDUCE is requested, a new state is not created, and the
                // action is marked as a Shift-reduce or a Goto-reduce. Otherwise
                // if a state with that kernel set does not yet exist, we create
                // it.
                //
                q = partition[symbol]; // kernel of a new state
                if (option.readReduce && q.next == null)
                {
                    int itemNo = q.value;
                    if (base.itemTable[itemNo].symbol == grammar.empty)
                    {
                        int ruleNo = base.itemTable[itemNo].ruleNumber;
                        if (grammar.rules.get(ruleNo).lhs != grammar.acceptImage)
                            action = -ruleNo;
                    }
                }

                if (action == Util.OMEGA) // Not a Read-Reduce action
                    action = lr0StateMap(q);

                //
                // At this stage, the partition list has been freed (for an old
                // state or an ADEQUATE item), or used (for a new state).  The
                // PARTITION field involved should be reset.
                //
                partition[symbol] = null;           // To be reused

                //
                // At this point, ACTION contains the value of the state to Shift
                // to, or rule to Read-Reduce on. If the symbol involved is a
                // terminal, we update the Shift map; else, it is a non-terminal
                // and we update the Goto map.
                // Shift maps are constructed temporarily in shiftAction.
                // Later, they are inserted into a map of unique Shift maps, and
                // shared by states that contain identical shifts.
                // Since the lookahead set computation is based on the GOTO maps,
                // all these maps and their element maps should be kept as
                // separate entities.
                //
                if (grammar.isTerminal(symbol)) // terminal? add to SHIFT map
                {
                    shiftAction[symbol] = action;
                    shiftList.add(symbol);
                    if (action > 0)
                        numShifts++;
                    else
                        numShiftReduces++;
                }
                //
                // NOTE that for Goto's we update the field LA_PTR of GOTO. This
                // field will be used later in the routine MKRDCTS to point to a
                // look-ahead set.
                //
                else
                {
                    state.goTo.add(new GotoTriplet(symbol, action, Util.OMEGA));

                    if (action > 0)
                        numGotos++;
                    else
                        numGotoReduces++;
                }
            }

            state.shiftNumber = updateShiftMaps(shiftList, shiftAction);

            //
            // Reset shiftList and shiftAction for reuse later...
            //
            for (int j = 0, n = shiftList.size(); j < n; j++)
            {
                int symbol = shiftList.get(j);
                shiftAction[symbol] = Util.OMEGA;
            }
            shiftList.clear();
        }

        //
        // Construct STATSET, a "compact" and final representation of
        // State table, and SHIFT which is a set of all shift maps needed.
        // NOTE that assignments to elements of SHIFT may occur more than
        // once, but that's ok. It is probably faster to  do that than to
        // set up an elaborate scheme to avoid the multiple assignment which
        // may in fact cost more.  Look at it this way: it is only a pointer
        // assignment, namely a Load and a Store.
        // Release all NODEs used by  the maps CLITEMS and CLOSURE.
        //
        // If the grammar is LALR(k), k > 1, more states may be added and
        // the size of the shift map increased.
        //
        numStates = statset.size() - 1; // recall that the 0th element is not used!

        assert (numShiftMaps == shift.size() - 1);
    }

    //
    // LR0_STATE_MAP takes as an argument a pointer to a kernel set of items. If
    // no state based on that kernel set already exists, then a new one is
    // created and added to STATSET. In any case, a pointer to the STATE of
    // the KERNEL is returned.
    //
    private int lr0StateMap(Node kernel)
    {
        //
        // Check whether a state is already defined by the KERNEL set.
        //
        StateElement state = statset.find(kernel);
        if (state == null)
        {
            //
            // Add a new state based on the KERNEL set.
            //
            state = new StateElement(kernel, statset.size());
            state.transitionSymbol = (base.itemTable[kernel.value].dot == 0
                                        ? grammar.empty
                                        : base.itemTable[kernel.value - 1].symbol);
            statset.insert(kernel, state);
        }
        return state.stateIndex;
    }

    //
    // We are now going to update the set of Shift-maps. Ths idea is
    // to do a look-up in a hash table based on SHIFT_TABLE to see if
    // the Shift map associated with the current state has already been
    // computed. If it has, we simply update the SHIFT_NUMBER and the
    // SHIFT field of the current state. Otherwise, we allocate and
    // construct a SHIFT_ELEMENT map, update the current state, and
    // add it to the set of Shift maps in the hash table.
    //   Note that the SHIFT_NUMBER field in the STATE_ELEMENTs could
    // have been factored out and associated instead with the
    // SHIFT_ELEMENTs. That would have saved some space, but only in
    // the short run. This field was purposely stored in the
    // STATE_ELEMENTs, because once the states have been constructed,
    // they are not kept, whereas the SHIFT_ELEMENTs are kept.
    //    One could have also threaded through the states that contain
    // original shift maps so as to avoid duplicate assignments in
    // creating the SHIFT map later. However, this would have
    // increased the storage requirement, and would probably have saved
    // (at most) a totally insignificant amount of time.
    //
    int updateShiftMaps(IntArrayList shiftList, int[] shiftAction)
    {
        if (shiftList.isEmpty())
            return 0;

        ShiftHeader shiftHeader = new ShiftHeader(shiftList, shiftAction, shift.size());
        shiftHeader = shift.findOrInsert(shiftHeader);
        if (!shiftHeader.isCompleted())
        {
            numShiftMaps++;
            assert (shiftHeader.poolIndex == numShiftMaps);

            shiftHeader.complete();
        }
        return shiftHeader.poolIndex;
    }

    int mapConflict(ConflictCell[] cell)
    {
        assert (cell.length > 1);
        Util.sort(cell);

        ConflictElement conflictElement = new ConflictElement(cell, conflicts);
        conflictElement = conflictElements.findOrInsert(conflictElement);
        if (!conflictElement.isCompleted())
            conflictElement.complete();

        return conflictElement.index;
    }

    //
    // Replace a conflict list with new list.
    //
    void remapConflict(int index, List<ConflictCell> cell)
    {
        assert (conflicts.get(index + cell.size()) == 0);
        for (int i = 0, n = cell.size(); i < n; i++)
            conflicts.set(index + i, cell.get(i).action);
    }

    //
    // We construct the IN_STAT map which is the inverse of the transition
    // map formed by GOTO and SHIFT maps.
    // This map is implemented as a table of pointers that can be indexed
    // by the states to a circular list of integers representing other
    // states that contain transitions to the state in question.
    //
    void buildPredecessorsMap()
    {
        for (int k = 1; k <= numStates; k++)
            statset.element(k).predecessors.clear();

        //
        // Construct map.
        //
        for (int stateNo = 1; stateNo <= numStates; stateNo++)
        {
            ShiftHeader sh = shift(stateNo);
            if (sh != null)
            {
                for (int i = 0, n = sh.size(); i < n; ++i)
                {
                    int action = sh.get(i).action();
                    if (action > 0 && action <= numStates) // A shift action?
                        addPredecessor(action, stateNo);
                }
            }

            GotoHeader goTo = statset.element(stateNo).goTo;
            for (int j = 0, m = goTo.size(); j < m; j++)
            {
                int action = goTo.get(j).action();
                if (action > 0) // A goto action
                    addPredecessor(action, stateNo);
            }
        }
    }

    //
    // Given a STATE_NO and an itemNo, ACCESS computes the set of states where
    // the rule from which itemNo is derived was introduced through closure.
    //
    void access(IntArrayList stateList, int stateNo, int itemNo)
    {
        //
        // Build a list pointed to by ACCESS_ROOT originally consisting
        // only of STATE_NO.
        //
        IntArrayList tempList = new IntArrayList();
        tempList.add(stateNo);
        int firstIndex = 0;
        for (int i = base.itemTable[itemNo].dot; i > 0; i--) // distance to travel is DOT
        {
            int n = tempList.size();
            for (int j = firstIndex; j < n; j++)
            {
                int stateNumber = tempList.get(j);
                //
                // Compute set of states with transition into p->value.
                //
                tempList.addAll(statset.element(stateNumber).predecessors);
            }

            firstIndex = n;
        }

        stateList.clear(); // clear the list out
        stateList.addAll(tempList);
    }

    //
    // PrintItem takes as parameter a text buffer and an itemNo. It formats and
    // outputs the item in question to the buffer.
    //
    void formatItem(StringBuilder buffer, int itemNo)
    {
        //
        // We first format the left hand side of the rule, leaving at least
        // 5 spaces in the output line to accomodate the equivalence symbol
        // "::=" surrounded by blanks on both sides.  Then, we format all the
        // terminal symbols in the right hand side up to but not including
        // the dot symbol.
        //
        int ruleNo = base.itemTable[itemNo].ruleNumber;
        Grammar.RuleElement rule = grammar.rules.get(ruleNo);
        int symbol = rule.lhs;
        grammar.restoreSymbol(buffer, grammar.retrieveString(symbol));
        buffer.append(rule.isArrowProduction() ? "." : " ::= ");
        for (int i = 0; i < base.itemTable[itemNo].dot; i++)
        {
            symbol = grammar.rhsSym.get(rule.rhsIndex + i);
            grammar.restoreSymbol(buffer, grammar.retrieveString(symbol));
            buffer.append(' ');
        }

        //
        // We now add a DOT "." to the output line and print the remaining
        // symbols in the right hand side.  If itemNo is a complete item,
        // we also print the rule number.
        //
        if (base.itemTable[itemNo].dot == 0 || base.itemTable[itemNo].symbol == grammar.empty)
            buffer.append('.');
        else
            buffer.append(" .");
        for (int k = rule.rhsIndex + base.itemTable[itemNo].dot, // symbols after dot
                 m = grammar.rules.get(ruleNo + 1).rhsIndex;
             k < m;
             k++)
        {
            symbol = grammar.rhsSym.get(k);
            grammar.restoreSymbol(buffer, grammar.retrieveString(symbol));
            buffer.append(' ');
        }

        if (base.itemTable[itemNo].symbol == grammar.empty)   // complete item
        {
            buffer.append(" (");
            buffer.append(ruleNo);
            buffer.append(')');
        }
    }

    //
    // PrintItem takes as parameter an itemNo which it formats and prints
    //
    void printItem(int itemNo)
    {
        StringBuilder tempstr = new StringBuilder(Control.PRINT_LINE_SIZE);
        StringBuilder line = new StringBuilder(Control.PRINT_LINE_SIZE);
        StringBuilder tok = new StringBuilder(Control.SYMBOL_SIZE);
        //
        // We first print the left hand side of the rule, leaving at least
        // 5 spaces in the output line to accomodate the equivalence symbol
        // "::=" surrounded by blanks on both sides.  Then, we print all the
        // terminal symbols in the right hand side up to but not including
        // the dot symbol.
        //
        int ruleNo = base.itemTable[itemNo].ruleNumber;
        Grammar.RuleElement rule = grammar.rules.get(ruleNo);
        grammar.restoreSymbol(tok, grammar.retrieveString(rule.lhs));

        int len = Control.PRINT_LINE_SIZE - 5;
        grammar.printLargeToken(line, tok, "", len);
        line.append(rule.isArrowProduction() ? "." : " ::= ");

        int i = (Control.PRINT_LINE_SIZE / 2) - 1;
        int offset = Math.min(line.length() - 1, i);
        len = Control.PRINT_LINE_SIZE - (offset + 4);

        i = rule.rhsIndex;  // symbols before dot
        int k = ((rule.rhsIndex + base.itemTable[itemNo].dot) - 1);
        try
        {
            for (; i <= k; i++)
            {
                int symbol = grammar.rhsSym.get(i);
                grammar.restoreSymbol(tok, grammar.retrieveString(symbol));
                if (tok.length() + line.length() > Control.PRINT_LINE_SIZE - 4)
                {
                    option.syslis.write(Util.LINE_SEPARATOR);
                    option.syslis.write(new String(line));
                    line.delete(0, line.length());

                    Util.fillIn(tempstr, offset, ' ');
                    grammar.printLargeToken(line, tok, tempstr, len);
                }
                else
                    line.append(tok);
                line.append(' ');
            }

            //
            // We now add a DOT "." to the output line and print the remaining
            // symbols in the right hand side.  If itemNo is a complete item,
            // we also print the rule number.
            //
            if (base.itemTable[itemNo].dot == 0 || base.itemTable[itemNo].symbol == grammar.empty)
                line.append('.');
            else
                line.append(" .");

            len = Control.PRINT_LINE_SIZE - (offset + 1);
            i = rule.rhsIndex + base.itemTable[itemNo].dot; // symbols after dot
            for (int n = grammar.rules.get(ruleNo + 1).rhsIndex; i < n; i++)
            {
                int symbol = grammar.rhsSym.get(i);
                grammar.restoreSymbol(tok, grammar.retrieveString(symbol));
                if (tok.length() + line.length() > Control.PRINT_LINE_SIZE - 1)
                {
                    option.syslis.write(Util.LINE_SEPARATOR);
                    option.syslis.write(new String(line));
                    line.delete(0, line.length());

                    Util.fillIn(tempstr, offset, ' ');
                    grammar.printLargeToken(line, tok, tempstr, len);
                }
                else
                    line.append(tok);
                line.append(' ');
            }

            if (base.itemTable[itemNo].symbol == grammar.empty)   // complete item
            {
                String num = String.valueOf(ruleNo);
                if (num.length() + line.length() > Control.PRINT_LINE_SIZE - 4)
                {
                    option.syslis.write(Util.LINE_SEPARATOR);
                    option.syslis.write(new String(line));
                    Util.fillIn(line, offset, ' ');
                }
                line.append(" (");
                line.append(num);
                line.append(")");
            }
            option.syslis.write(Util.LINE_SEPARATOR);
            option.syslis.write(new String(line));
        }
        catch (IOException e)
        {
        }
    }

    ShiftHeader shift(int stateNo)
    {
        return shift.element(statset.element(stateNo).shiftNumber);
    }

    void addPredecessor(int nextStateNo, int stateNo)
    {
        statset.element(nextStateNo).predecessors.add(stateNo);
    }

    final LookupTable<Node, StateElement> statset = new LookupTable<Node, StateElement>();
    final LookupSet<ShiftHeader> shift = new LookupSet<ShiftHeader>();
    final IntArrayList conflicts = new IntArrayList();

    final Control control;
    final Option option;
    final Grammar grammar;
    final Base base;

    int numStates = 0;
    int numShiftMaps = 0;
    int numShifts = 0;
    int numGotos = 0;
    int numShiftReduces = 0;
    int numGotoReduces = 0;

    private LookupSet<ConflictElement> conflictElements = new LookupSet<ConflictElement>();

    static class ShiftPair
    {
        ShiftPair(int symbol, int action)
        {
            this.symbol = symbol;
            this.action = action;
        }

        int symbol()
        {
            return symbol;
        }

        int action()
        {
            return action;
        }

        void setSymbol(int symbol)
        {
            this.symbol = symbol;
        }

        void setAction(int action)
        {
            this.action = action;
        }

        private int symbol = 0;
        private int action = 0;
    }

    static class ShiftHeader extends ArrayList<ShiftPair>
    {
        ShiftHeader(IntArrayList shiftList, int[] shiftAction, int poolIndex)
        {
            this.shiftList = shiftList;
            this.shiftAction = shiftAction;
            this.poolIndex = poolIndex;
        }

        int index(int symbol)
        {
            for (int i = 0, n = size(); i < n; i++)
            {
                if (get(i).symbol() == symbol)
                    return i;
            }
            return Util.OMEGA;
        }

        int action(int symbol)
        {
            for (int i = 0, n = size(); i < n; i++)
            {
                ShiftPair shiftPair = get(i);
                if (shiftPair.symbol() == symbol)
                    return shiftPair.action();
            }
            return Util.OMEGA;
        }

        boolean isCompleted()
        {
            return shiftList == null;
        }

        void complete()
        {
            for (int i = 0, n = shiftList.size(); i < n; i++)
            {
                int symbol = shiftList.get(i);
                add(new ShiftPair(symbol, shiftAction[symbol]));
            }
            shiftList = null;
            shiftAction = null;
        }

        public boolean equals(Object obj)
        {
            if (obj == this)
                return true;
            if (!(obj instanceof ShiftHeader))
                return false;

            return compare((ShiftHeader)obj);
        }

        private boolean compare(ShiftHeader shiftHeader)
        {
            int size = shiftList.size();
            if (size != shiftHeader.size())
                return false;
            for (int i = 0; i < size; i++)
            {
                ShiftPair shiftPair = shiftHeader.get(i);
                if (shiftAction[shiftPair.symbol] != shiftPair.action)
                    return false;
            }
            return true;
        }

        public int hashCode()
        {
            int result;
            if (shiftList != null)
            {
                result = shiftList.size();
                for (int i = 0, n = result; i < n; i++)
                    result = 31 * result + Math.abs(shiftAction[shiftList.get(i)]);
            }
            else
            {
                result = size();
                for (int i = 0, n = result; i < n; i++)
                    result = 31 * result + Math.abs(get(i).action);
            }
            return result;
        }

        private IntArrayList shiftList = null;
        private int[] shiftAction = null;
        private final int poolIndex;
    }

    static class GotoTriplet
    {
        GotoTriplet(int symbol, int action, int laptr)
        {
            this.symbol = symbol;
            this.action = action;
            this.laptr  = laptr;
        }

        int symbol()
        {
            return symbol;
        }

        int action()
        {
            return action;
        }

        int laptr()
        {
            return laptr;
        }

        void setSymbol(int symbol)
        {
            this.symbol = symbol;
        }

        void setAction(int action)
        {
            this.action = action;
        }

        void setLaptr(int laptr)
        {
            this.laptr = laptr;
        }

        private int symbol = 0;
        private int action = 0;
        private int laptr  = 0;
    }

    static class GotoHeader extends ArrayList<GotoTriplet>
    {
        int index(int symbol)
        {
            for (int i = 0, n = size(); i < n; i++)
            {
                if (get(i).symbol() == symbol)
                    return i;
            }
            return Util.OMEGA;
        }

        int action(int symbol)
        {
            for (int i = 0, n = size(); i < n; i++)
            {
                GotoTriplet gotoTriplet = get(i);
                if (gotoTriplet.symbol() == symbol)
                    return gotoTriplet.action();
            }
            return Util.OMEGA;
        }

        void removeDefaults(BoundedIntArray gotoDefault)
        {
            int lastIndex = size() - 1;
            for (int i = lastIndex; i >= 0; i--)
            {
                //
                // If the action matches the default, remove it
                //
                GotoTriplet gotoTriplet = get(i);
                if (gotoDefault.get(gotoTriplet.symbol()) == gotoTriplet.action())
                {
                    GotoTriplet lastGotoTriplet = get(lastIndex);
                    gotoTriplet.setSymbol(lastGotoTriplet.symbol());
                    gotoTriplet.setAction(lastGotoTriplet.action());
                    remove(lastIndex--);
                }
            }
        }
    }

    static class Reduce
    {
        int symbol()
        {
            return symbol;
        }

        int ruleNumber()
        {
            return ruleNumber;
        }

        void setSymbol(int symbol)
        {
            this.symbol = symbol;
        }

        void setRuleNumber(int ruleNumber)
        {
            this.ruleNumber = ruleNumber;
        }

        private int symbol = 0;
        private int ruleNumber = 0;
    }

    static class ReduceHeader extends ArrayList<Reduce>
    {
        int index(int symbol)
        {
            for (int i = 0, n = size(); i < n; i++)
            {
                if (get(i).symbol() == symbol)
                    return i;
            }
            return Util.OMEGA;
        }

        int ruleNumber(int symbol)
        {
            for (int i = 0, n = size(); i < n; i++)
            {
                Reduce reduce = get(i);
                if (reduce.symbol() == symbol)
                    return reduce.ruleNumber();
            }
            return Util.OMEGA;
        }
    }

    static class Conflict
    {
        int symbol()
        {
            return symbol;
        }

        int conflictIndex()
        {
            return conflictIndex;
        }

        void setSymbol(int symbol)
        {
            this.symbol = symbol;
        }

        void setConflictIndex(int conflictIndex)
        {
            this.conflictIndex = conflictIndex;
        }

        private int symbol = 0;
        private int conflictIndex = 0;
    }

    static class ConflictHeader extends ArrayList<Conflict>
    {
        int index(int symbol)
        {
            for (int i = 0, n = size(); i < n; i++)
            {
                if (get(i).symbol() == symbol)
                    return i;
            }
            return Util.OMEGA;
        }

        int conflictIndex(int symbol)
        {
            for (int i = 0, n = size(); i < n; i++)
            {
                Conflict conflict = get(i);
                if (conflict.symbol() == symbol)
                    return conflict.conflictIndex();
            }
            return Util.OMEGA;
        }
    }

    static class ConflictCell implements Comparable<ConflictCell>
    {
        int action = 0;
        int priority = 0;

        public int compareTo(ConflictCell c)
        {
            return (priority < c.priority ? -1 : (priority == c.priority ? 0 : 1));
        }
    }

    static class StateElement
    {
        StateElement(Node kernelItems, int stateIndex)
        {
            this.kernelItems = kernelItems;
            this.stateIndex = stateIndex;
        }

        final Node kernelItems;
        final int stateIndex;

        Node completeItems = null;
        Node singleProductionItems = null;
        IntArrayList predecessors = new IntArrayList();
        GotoHeader goTo = new GotoHeader();
        ReduceHeader reduce = new ReduceHeader();
        ConflictHeader conflict = new ConflictHeader();
        IntArrayList softKeywords = new IntArrayList();
        int shiftNumber = 0;
        int transitionSymbol = 0;
    }

    private static class ConflictElement
    {
        ConflictElement(ConflictCell[] cell, IntArrayList conflicts)
        {
            this.cell = cell;
            this.conflicts = conflicts;
        }

        boolean isCompleted()
        {
            return cell == null;
        }

        void complete()
        {
            index = conflicts.size();

            for (int i = 0, n = cell.length; i < n; i++)
                conflicts.add(cell[i].action);
            conflicts.add(0);

            cell = null;
        }

        public boolean equals(Object obj)
        {
            if (obj == this)
                return true;
            if (!(obj instanceof ConflictElement))
                return false;

            return compare((ConflictElement)obj);
        }

        private boolean compare(ConflictElement conflictElement)
        {
            int idx = conflictElement.index;
            for (int i = 0, n = cell.length; i < n; i++)
            {
                if (conflicts.get(idx + i) != cell[i].action)
                    return false;
            }
            return (conflicts.get(idx + cell.length) == 0);
        }

        public int hashCode()
        {
            int result = 1;
            if (cell != null)
            {
                for (int i = 0, n = cell.length; i < n; i++)
                    result = 31 * result + Math.abs(cell[i].action);
            }
            else
            {
                for (int i = index, act; (act = conflicts.get(i)) != 0; i++)
                    result = 31 * result + Math.abs(act);
            }
            return result;
        }

        private final IntArrayList conflicts;
        int index = 0;

        private ConflictCell[] cell = null;
    }

}
